<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title> - 友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="查找 1. 什么是查找  查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。  除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。
 平均查找长度ASL（Average Search Length）：关键字的平均比较次数。  2. 静态查找与动态查找 查找的目的：
 查询特定数据是否在查找表中 检索查找表中某个特定数据的属性 在查找表中插入一个数据元素 在查找表中删除某个数据元素   静态查找（static search）：仅对查找表进行上述的前两种查找操作 动态查找（dynamic search）：存在上述的第3种或第4种查找操作  3. 查找相关的数据结构对比  线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
 时间复杂度：O(n) 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
 时间复杂度：O(logn) 空间复杂度：O(1)，非递归实现  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
 时间复杂度：log(n/s) &#43; s，s为每块元素数量 空间复杂度：O(n/s)   平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。   二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。 AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。 RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。  二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。
 AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。  AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n&#43;1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。" />

  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/08%E6%9F%A5%E6%89%BE/" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="" />
<meta property="og:description" content="查找 1. 什么是查找  查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。  除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。
 平均查找长度ASL（Average Search Length）：关键字的平均比较次数。  2. 静态查找与动态查找 查找的目的：
 查询特定数据是否在查找表中 检索查找表中某个特定数据的属性 在查找表中插入一个数据元素 在查找表中删除某个数据元素   静态查找（static search）：仅对查找表进行上述的前两种查找操作 动态查找（dynamic search）：存在上述的第3种或第4种查找操作  3. 查找相关的数据结构对比  线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
 时间复杂度：O(n) 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
 时间复杂度：O(logn) 空间复杂度：O(1)，非递归实现  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
 时间复杂度：log(n/s) &#43; s，s为每块元素数量 空间复杂度：O(n/s)   平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。   二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。 AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。 RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。  二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。
 AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。  AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n&#43;1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/08%E6%9F%A5%E6%89%BE/" />

<meta itemprop="name" content="">
<meta itemprop="description" content="查找 1. 什么是查找  查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。  除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。
 平均查找长度ASL（Average Search Length）：关键字的平均比较次数。  2. 静态查找与动态查找 查找的目的：
 查询特定数据是否在查找表中 检索查找表中某个特定数据的属性 在查找表中插入一个数据元素 在查找表中删除某个数据元素   静态查找（static search）：仅对查找表进行上述的前两种查找操作 动态查找（dynamic search）：存在上述的第3种或第4种查找操作  3. 查找相关的数据结构对比  线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
 时间复杂度：O(n) 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
 时间复杂度：O(logn) 空间复杂度：O(1)，非递归实现  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
 时间复杂度：log(n/s) &#43; s，s为每块元素数量 空间复杂度：O(n/s)   平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。   二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。 AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。 RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。  二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。
 AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。  AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n&#43;1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。">



<meta itemprop="wordCount" content="111">



<meta itemprop="keywords" content="" />
<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content=""/>
<meta name="twitter:description" content="查找 1. 什么是查找  查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。  除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。
 平均查找长度ASL（Average Search Length）：关键字的平均比较次数。  2. 静态查找与动态查找 查找的目的：
 查询特定数据是否在查找表中 检索查找表中某个特定数据的属性 在查找表中插入一个数据元素 在查找表中删除某个数据元素   静态查找（static search）：仅对查找表进行上述的前两种查找操作 动态查找（dynamic search）：存在上述的第3种或第4种查找操作  3. 查找相关的数据结构对比  线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）  线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。
 时间复杂度：O(n) 空间复杂度：O(1)  线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。
 时间复杂度：O(logn) 空间复杂度：O(1)，非递归实现  线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。
 时间复杂度：log(n/s) &#43; s，s为每块元素数量 空间复杂度：O(n/s)   平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。   二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。 AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。 RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。  二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。
 AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。 红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。  AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n&#43;1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。"/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          <article class="post bg-white">
    
    <header class="post-header">
      <h1 class="post-title"></h1>
      
      <div class="post-meta">
        <time datetime="0001-01-01" class="post-time">
          0001-01-01
        </time>
        
        <span class="more-meta"> 约 111 字 </span>
          <span class="more-meta"> 预计阅读 1 分钟 </span>

        
        

        
        
      </div>
    </header>

    
    
<div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">文章目录</h2>
  <div class="post-toc-content">
    <nav id="TableOfContents">
<ul>
<li><a href="#查找">查找</a>
<ul>
<li><a href="#1-什么是查找">1. 什么是查找</a></li>
<li><a href="#2-静态查找与动态查找">2. 静态查找与动态查找</a></li>
<li><a href="#3-查找相关的数据结构对比">3. 查找相关的数据结构对比</a></li>
<li><a href="#参考">参考</a></li>
</ul></li>
</ul>
</nav>
  </div>
</div>

    
    <div class="post-content">
      

<h1 id="查找">查找</h1>

<h2 id="1-什么是查找">1. 什么是查找</h2>

<ul>
<li>查找：事先给定一个值，在查找表（同一类型的数据元素构成的集合）中找到其关键字等于给定值的数据元素（一个或多个）。</li>
</ul>

<p>除了时间复杂度和空间复杂度之外，通常还使用ASL来衡量查找算法的好坏程度。</p>

<ul>
<li>平均查找长度ASL（Average Search Length）：关键字的平均比较次数。</li>
</ul>

<h2 id="2-静态查找与动态查找">2. 静态查找与动态查找</h2>

<p>查找的目的：</p>

<ol>
<li>查询特定数据是否在查找表中</li>
<li>检索查找表中某个特定数据的属性</li>
<li>在查找表中插入一个数据元素</li>
<li>在查找表中删除某个数据元素</li>
</ol>

<ul>
<li>静态查找（static search）：仅对查找表进行上述的前两种查找操作</li>
<li>动态查找（dynamic search）：存在上述的第3种或第4种查找操作</li>
</ul>

<h2 id="3-查找相关的数据结构对比">3. 查找相关的数据结构对比</h2>

<ol>
<li>线性表：线性表中效率最好的二分查找为O(logn)，但是对动态查找支持不好（要求有序并且是顺序表，插入删除操作需要大量元素移动）</li>
</ol>

<p>线性表的顺序查找适用场景较广，但是效率相对较低。若是动态查找场景，可以采用链表实现，避免大量元素移动；并且由于线性表中元素无序，所以即使是采用顺序存储，新增时也不会产生大量元素移动。</p>

<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1)</li>
</ul>

<p>线性表的二分查找效率较好，但是适用场景单一（要求有序并且是顺序表），对于动态查找场景（大量插入和删除）需要移动大量元素。</p>

<ul>
<li>时间复杂度：O(logn)</li>
<li>空间复杂度：O(1)，非递归实现</li>
</ul>

<p>线性表分块索引查找性能介于顺序查找和二分查找之间。对于动态查找场景，插入、删除较为容易，无需进行大量元素移动。但需要引入额外的索引存储空间，并对初始索引进行排序计算。</p>

<ul>
<li>时间复杂度：log(n/s) + s，s为每块元素数量</li>
<li>空间复杂度：O(n/s)</li>
</ul>

<ol>
<li>平衡二叉树（AVL）与红黑树：如果希望拥有与折半查找同样的查找效率O(logn)，并且对频繁的插入删除操作不需要大量元素移动，可以使用AVL或红黑树。</li>
</ol>

<ul>
<li>二叉排序树：时间复杂度最佳情况是 O(log­n)，而最坏情况是 O(n)。空间复杂度是O(n)，因为有指针。</li>
<li>AVL：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及平衡因子。</li>
<li>RBtree：查找、插入和删除在平均和最坏情况下都是O（log n）。空间复杂度是O(n)，因为有指针及颜色标记。</li>
</ul>

<p>二叉查找树最坏查找次数是树的深度。其平均查找长度与树的形态有关，树的高度越高，平均查找长度越长，最佳情况是 O(log­2n)——树比较平衡的状态，而最坏情况是 O(n)——即退化成为线性顺序查找。</p>

<ul>
<li>AVL树：一般是用平衡因子差值决定并通过旋转来实现，左右子树树高差不超过1，那么和红黑树比较它是严格的平衡二叉树，平衡条件非常严格（树高差只有1），只要插入或删除不满足上面的条件就要通过旋转来保持平衡。由于旋转是非常耗费时间的。我们可以推出AVL树适合用于插入删除次数比较少，但查找多的情况。</li>
<li>红黑树：通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长2倍，因而是近似平衡的。所以相对于严格要求平衡的AVL树来说，它的旋转保持平衡次数较少。用于搜索时，插入删除次数多的情况下我们就用红黑树来取代AVL。</li>
</ul>

<p>AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。红黑树平衡度没AVL那么好。也就是说，如果从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于AVL的。数学证明红黑树的最大深度是 2log(2n+1), 其实最差情况它从根到叶子的最长路可以是最短路的两倍，但也不是很差，所以它的查询时间复杂度也是O（log n）。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。</p>

<ul>
<li>如果要较真比较性能的话，如果是有大量查询的场合，AVL可能好一些；不过如果要维护动态树结构的话，红黑树通常更好，因为对平衡性的要求不是那么严格，树结构变化时调整的次数相对较少。</li>
</ul>

<p>windows对进程地址空间的管理用到了AVL树。红黑树广泛用在C++的STL中，如map和set都是用红黑树实现的。</p>

<ol>
<li>B树与B+树：在大规模数据、持久化存储场景中，如果希望在保持O(logn)查找效率的情况下，同时减少每次查询IO操作的次数，可以使用B+树。</li>
</ol>

<ul>
<li>时间复杂度：查找、插入和删除在平均和最坏情况下都是O（log n）</li>
<li>空间复杂度：O(n)，因为有指针（B树还有关键字）</li>
</ul>

<p>大规模数据的持久化存储中，二叉查找树、AVL和红黑树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么如何减少树的深度，一个基本的想法就是：采用多叉树结构。</p>

<blockquote>
<p>以数据库索引的存储结构设计来举例。我们给一亿个数据构建二叉查找树索引，那索引中会包含大约 1 亿个节点，每个节点假设占用 16 个字节，那就需要大约 1GB 的内存空间。给一张表建立索引，我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引，那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢？
我们可以借助时间换空间的思路，把索引存储在硬盘中，而非内存中。我们都知道，硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的。读取同样大小的数据，从磁盘中读取花费的时间，是从内存中读取所花费时间的上万倍，甚至几十万倍。
这种将索引存储在硬盘中的方案，尽管减少了内存消耗，但是在数据查找的过程中，需要读取磁盘中的索引，因此数据查询效率就相应降低很多。
不过，为了节省内存，如果把树存储在硬盘中，那么每个节点的读取（或者访问），都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。
我们来看下，如果我们把索引构建成 m 叉树，高度是不是比二叉树要小呢？比如，给 16 个数据构建二叉树索引，树的高度是 4，查找一个数据，就需要 4 个磁盘 IO 操作（如果根节点存储在内存中，其他结点存储在磁盘中），如果对 16 个数据构建五叉树索引，那高度只有 2，查找一个数据，对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100，那对一亿个数据构建索引，树的高度也只是 3，最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了，查找数据的效率也就提高了。</p>
</blockquote>

<p>B/B+ 树就是N叉（N-ary）平衡树，每个节点可以有更多的孩子，新的值可以插在已有的节点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。</p>

<p>B树与B+树用在磁盘文件组织、数据索引和数据库索引。</p>

<ol>
<li>散列表：查找效率更高O(1)，但是存在空间浪费，并且Hash表本身是无序的，没办法进行区间查找。</li>
</ol>

<ul>
<li>红黑树查找和删除的时间复杂度都是O(logn)，Hash查找和删除的时间复杂度都是O(1)。</li>
<li>树表是有序的，Hash表是无序的</li>
<li>红黑树占用的内存更小（仅需要为其存在的节点分配内存），而Hash事先就应该分配足够的内存存储散列表（即使有些槽可能遭弃用）。</li>
</ul>

<h2 id="参考">参考</h2>

<p><a href="https://www.zhihu.com/question/30527705/answer/259948086，韦易笑">https://www.zhihu.com/question/30527705/answer/259948086，韦易笑</a></p>

    </div>

    
    
<div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">文章作者</span>
    <span class="item-content">yixy</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">上次更新</span>
    <span class="item-content">
      0001-01-01
      
    </span>
  </p>
  
  <p class="copyright-item">
    <span class="item-title">许可协议</span>
    <span class="item-content"><a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank">CC BY-NC-ND 4.0</a></span>
  </p>
</div>


    
    
<div class="post-reward">
  <input type="checkbox" name="reward" id="reward" hidden />
  <label class="reward-button" for="reward">赞赏支持</label>
  <div class="qr-code">
    
    
      <label class="qr-code-image" for="reward">
        <img class="image" src="/youzhilane/img/about/wechat.jpg">
        <span>微信打赏</span>
      </label>
    
  </div>
</div>

    <footer class="post-footer">
      

      
      <nav class="post-nav">
        
          <a class="prev" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/07%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%9B%BE/">
            
            <i class="iconfont">
              <svg  class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M691.908486 949.511495l75.369571-89.491197c10.963703-12.998035 10.285251-32.864502-1.499144-44.378743L479.499795 515.267417 757.434875 204.940602c11.338233-12.190647 11.035334-32.285311-0.638543-44.850487l-80.46666-86.564541c-11.680017-12.583596-30.356378-12.893658-41.662889-0.716314L257.233596 494.235404c-11.332093 12.183484-11.041474 32.266891 0.657986 44.844348l80.46666 86.564541c1.772366 1.910513 3.706415 3.533476 5.750981 4.877077l306.620399 321.703933C662.505829 963.726242 680.945807 962.528973 691.908486 949.511495z"></path>
</svg>

            </i>
            <span class="prev-text nav-default"></span>
            <span class="prev-text nav-mobile">上一篇</span>
          </a>
        
          <a class="next" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/09%E7%BA%BF%E6%80%A7%E8%A1%A8%E6%9F%A5%E6%89%BE%E9%A1%BA%E5%BA%8F%E6%9F%A5%E6%89%BE/">
            <span class="next-text nav-default"></span>
            <span class="prev-text nav-mobile">下一篇</span>
            
            <i class="iconfont">
              <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M332.091514 74.487481l-75.369571 89.491197c-10.963703 12.998035-10.285251 32.864502 1.499144 44.378743l286.278095 300.375162L266.565125 819.058374c-11.338233 12.190647-11.035334 32.285311 0.638543 44.850487l80.46666 86.564541c11.680017 12.583596 30.356378 12.893658 41.662889 0.716314l377.434212-421.426145c11.332093-12.183484 11.041474-32.266891-0.657986-44.844348l-80.46666-86.564541c-1.772366-1.910513-3.706415-3.533476-5.750981-4.877077L373.270379 71.774697C361.493148 60.273758 343.054193 61.470003 332.091514 74.487481z"></path>
</svg>

            </i>
          </a>
      </nav>
    </footer>
  </article>

  
  
  
  

  
  

  

  
  

  

  

  

    

  

        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
